package Sequence;

import java.util.ArrayList;
import java.util.List;

public class Test0093 {
    public static void main(String[] args) {
        new Solution0093_1().restoreIpAddresses("101023");
    }
}

class Solution0093_1 {
    List<String> ans = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backtrack(new StringBuilder(),s,0,1);
        return ans;
    }

    public void backtrack(StringBuilder stringBuilder, String s,int start,int count) {
        int length = s.length();
        int temp = stringBuilder.length();
        if (count == 4) {
            if (isRegular(s,start,length)) {
                stringBuilder.append(s.substring(start));
                ans.add(stringBuilder.toString());
                stringBuilder.setLength(temp);
            }
        }else {
            for (int i = start+1; i < length&&4-count<=length-i; i++) {
                if (isRegular(s,start,i)) {
                    if ((i-start)<4&& (length-i)/(4-count)<=3) {
                        stringBuilder.append(s, start, i).append(".");
                        backtrack(stringBuilder,s,i,count+1);
                        stringBuilder.setLength(temp);
                    }
                }else {
                    return;
                }
            }
        }
    }

    public boolean isRegular(String s,int start,int end) {
        s = s.substring(start, end);
        if (end-start>3)
            return false;
        return (end-start==1||s.charAt(0)!='0')&& Integer.parseInt(s)<=255;
    }
}